Online Judge►LeetCode

[LeetCode] 144 - Binary Tree Preorder Traversal

題意

使用非遞迴的方式 Preorder Traversal 二元樹。

解法

Preorder 順序是根、左子樹、右子樹，利用 stack 來完成 Traversal 。

與 Inorder Traversal 解法類似，向左子樹尋找的路上不斷紀錄根節點，且將右子樹都先放到 stack 中

程式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
  if ( !root ) return [];
  
  let stack = [];
  let result = [];
  let node = root;
  
  while( stack.length !== 0 || node !== null ){
    if ( !node ){
      node = stack.pop();
    }
    result.push(node.val);
    if ( node.right ){
      stack.push(node.right);
    }
    node = node.left;
  }
  return result;
};